Set cover problem

 ( Families Of Sets ) 

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.

Given a set of elements (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as , of a given subsets whose union equals the universe, the set cover problem is to identify a smallest sub-collection of whose union equals the universe.

For example, consider the universe, and the collection of sets In this example, is equal to 4, as there are four subsets that comprise this collection. The union of is equal to . However, we can cover all elements with only two sets: , see picture, but not with only one set. Therefore, the solution to the set cover problem for this and has size 2.

More formally, given a universe $\backslash mathcal\{U\}$ and a family $\backslash mathcal\{S\}$ of subsets of $\backslash mathcal\{U\}$, a set cover is a subfamily $\backslash mathcal\{C\}\backslash subseteq\backslash mathcal\{S\}$ of sets whose union is $\backslash mathcal\{U\}$.

• In the set cover decision problem, the input is a pair $(\backslash mathcal\{U\},\backslash mathcal\{S\})$ and an integer $k$; the question is whether there is a set cover of size $k$ or less.
• In the set cover optimization problem, the input is a pair $(\backslash mathcal\{U\},\backslash mathcal\{S\})$, and the task is to find a set cover that uses the fewest sets.

The decision version of set covering is NP-complete. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. The optimization/search version of set cover is NP-hard. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.

---

Variants In the weighted set cover problem, each set is assigned a positive weight (representing its cost), and the goal is to find a set cover with a smallest weight. The usual (unweighted) set cover corresponds to all sets having a weight of 1.

In the fractional set cover problem, it is allowed to select fractions of sets, rather than entire sets. A fractional set cover is an assignment of a fraction (a number in 0,1) to each set in $\backslash mathcal\{S\}$, such that for each element x in the universe, the sum of fractions of sets that contain x is at least 1. The goal is to find a fractional set cover in which the sum of fractions is as small as possible. Note that a (usual) set cover is equivalent to a fractional set cover in which all fractions are either 0 or 1; therefore, the size of the smallest fractional cover is at most the size of the smallest cover, but may be smaller. For example, consider the universe and the collection of sets The smallest set cover has a size of 2, e.g. But there is a fractional set cover of size 1.5, in which a 0.5 fraction of each set is taken.

---

Linear program formulation The set cover problem can be formulated as the following integer linear program (ILP).

minimize	$\backslash sum\_\{s\; \backslash in\; \backslash mathcal\; S\}\; x\_s$		(minimize the number of sets)
subject to	$\backslash sum\_\{s\backslash colon\; e\; \backslash in\; s\}\; x\_s\; \backslash geqslant\; 1$	for all $e\backslash in\; \backslash mathcal\; U$	(cover every element of the universe)
	$x\_s\; \backslash in\; \backslash \{0,1\backslash \}$	for all $s\backslash in\; \backslash mathcal\; S$.	(every set is either in the set cover or not)

For a more compact representation of the covering constraint, one can define an incidence matrix $A$, where each row corresponds to an element and each column corresponds to a set, and $A\_\{e,s\}=1$ if element e is in set s, and $A\_\{e,s\}=0$ otherwise. Then, the covering constraint can be written as $A\; x\; \backslash geqslant\; 1$.

Weighted set cover is described by a program identical to the one given above, except that the objective function to minimize is $\backslash sum\_\{s\; \backslash in\; \backslash mathcal\; S\}\; w\_s\; x\_s$, where $w\_\{s\}$ is the weight of set $s\backslash in\; \backslash mathcal\{S\}$.

Fractional set cover is described by a program identical to the one given above, except that $x\_s$ can be non-integer, so the last constraint is replaced by $0\; \backslash leq\; x\_s\backslash leq\; 1$.

This linear program belongs to the more general class of LPs for , as all the coefficients in the objective function and both sides of the constraints are non-negative. The integrality gap of the ILP is at most $\backslash scriptstyle\; \backslash log\; n$ (where $\backslash scriptstyle\; n$ is the size of the universe). It has been shown that its relaxation indeed gives a factor-$\backslash scriptstyle\; \backslash log\; n$ approximation algorithm for the minimum set cover problem. See randomized rounding#setcover for a detailed explanation.

---

Hitting set formulation The set cover problem is equivalent to the hitting set problem. A subset $H$ of $U$ is called a hitting set when $H\; \backslash cap\; S\_j\; \backslash neq\; \backslash emptyset$ for all $1\; \backslash leq\; j\; \backslash leq\; m$ (i.e., $H$ intersects or “hits” all subsets in $S$). The hitting set problem is to find a minimum hitting set $H$ for a given $U$ and $S$.

To show that the problems are equivalent, for a universe $U$ of size $n$ and collection of sets $S$ of size $m$, construct $U\text{'}=\backslash \{1,2,\backslash ldots,m\backslash \}$ and $S\text{'}\_i\; =\; \backslash \{\; j\; \backslash mid\; i\; \backslash in\; S\_j\; \backslash \}$. Then a set cover $C$ of $S$ is equivalent to a hitting set $H\text{'}$ of $U\text{'}$ where $S\_j\; \backslash in\; C\; \backslash iff\; j\; \backslash in\; H\text{'}$, and vice versa.

This equivalence can also be visualized by representing the problem as a bipartite graph of $n\; +\; m$ vertices, with $n$ vertices on the left representing elements of $U$, and $m$ vertices on the right representing elements of $S$, and edges representing set membership (i.e., there is an edge between the $i$-th vertex on the left and the $j$-th vertex of the right iff. $i\; \backslash in\; S\_j$). Then a set cover is a subset $C$ of right vertices such that each left vertex is adjacent to at least one member of $C$, while a hitting set is a subset $H$ of left vertices such that each right vertex is adjacent to at least one member of $H$. These definitions are exactly the same except that left and right are swapped. But there is nothing special about the sides in the bipartite graph; we could have put the elements of $U$ on the right side, and the elements of $S$ on the left side, creating a graph that is a mirror image of the one described above. This shows that set covers in the original graph are equivalent to hitting sets in the mirrored graph, and vice versa.

In the field of computational geometry, a hitting set for a collection of geometrical objects is also called a stabbing set or piercing set.

---

Greedy algorithm There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a bucket queue to prioritize the sets. It achieves an approximation ratio of $H(s)$, where $s$ is the size of the set to be covered. In other words, it finds a covering that may be $H(n)$ times as large as the minimum one, where $H(n)$ is the $n$-th harmonic number: $$H(n)\; =\; \backslash sum\_\{k=1\}^\{n\}\; \backslash frac\{1\}\{k\}\; \backslash le\; \backslash ln\{n\}\; +1$$

This greedy algorithm actually achieves an approximation ratio of $H(s^\backslash prime)$ where $s^\backslash prime$ is the maximum cardinality set of $S$. For $\backslash delta-$dense instances, however, there exists a $c\; \backslash ln\{m\}$-approximation algorithm for every $c\; >\; 0$.

There is a standard example on which the greedy algorithm achieves an approximation ratio of $\backslash log\_2(n)/2$. The universe consists of $n=2^\{(k+1)\}-2$ elements. The set system consists of $k$ pairwise disjoint sets $S\_1,\backslash ldots,S\_k$ with sizes $2,4,8,\backslash ldots,2^k$ respectively, as well as two additional disjoint sets $T\_0,T\_1$, each of which contains half of the elements from each $S\_i$. On this input, the greedy algorithm takes the sets $S\_k,\backslash ldots,S\_1$, in that order, while the optimal solution consists only of $T\_0$ and $T\_1$. An example of such an input for $k=3$ is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results below), under plausible complexity assumptions. A tighter analysis for the greedy algorithm shows that the approximation ratio is exactly $\backslash ln\{n\}\; -\; \backslash ln\{\backslash ln\{n\}\}\; +\; \backslash Theta(1)$.Slavík Petr A tight analysis of the greedy algorithm for set cover. STOC'96, Pages 435-441,

---

Low-frequency systems If each element occurs in at most sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of using LP relaxation.

If the constraint $x\_S\backslash in\backslash \{0,1\backslash \}$ is replaced by $x\_S\; \backslash geq\; 0$ for all in $\backslash mathcal\{S\}$ in the integer linear program shown above, then it becomes a (non-integer) linear program . The algorithm can be described as follows:

1. Find an optimal solution for the program using some polynomial-time method of solving linear programs.
2. Pick all sets for which the corresponding variable has value at least 1/ in the solution .

---

Inapproximability results When $n$ refers to the size of the universe, showed that set covering cannot be approximated in polynomial time to within a factor of $\backslash tfrac\{1\}\{2\}\backslash log\_2\{n\}\; \backslash approx\; 0.72\backslash ln\{n\}$, unless NP has quasi-polynomial time algorithms. Uriel Feige (1998) improved this lower bound to $\backslash bigl(1-o(1)\backslash bigr)\backslash cdot\backslash ln\{n\}$ under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. established a lower bound of $c\backslash cdot\backslash ln\{n\}$, where $c$ is a certain constant, under the weaker assumption that P$\backslash not=$ NP. A similar result with a higher value of $c$ was recently proved by . showed optimal inapproximability by proving that it cannot be approximated to $\backslash bigl(1\; -\; o(1)\backslash bigr)\; \backslash cdot\; \backslash ln\{n\}$ unless P$=$ NP.

In low-frequency systems, proved it is NP-hard to approximate set cover to better than $f-1-\backslash epsilon$. If the Unique games conjecture is true, this can be improved to $f-\backslash epsilon$ as proven by .

proves that set cover instances with sets of size at most $\backslash Delta$ cannot be approximated to a factor better than $\backslash ln\; \backslash Delta\; -\; O(\backslash ln\; \backslash ln\; \backslash Delta)$ unless '''P'''$=$'''NP''', thus making the approximation of $\backslash ln\; \backslash Delta\; +\; 1$ of the greedy algorithm essentially tight in this case.
     

---

Weighted set cover Relaxing the integer linear program for weighted set cover stated above, one may use randomized rounding to get an $O(\backslash log\; n)$-factor approximation. Non weighted set cover can be adapted to the weighted case.

---

Fractional set cover

---

Related problems

• Hitting set is an equivalent reformulation of Set Cover.
• Vertex cover is a special case of Hitting Set.
• Edge cover is a special case of Set Cover.
• Geometric set cover is a special case of Set Cover when the universe is a set of points in $\backslash mathbb\{R\}^d$ and the sets are induced by the intersection of the universe and geometric shapes (e.g., disks, rectangles).
• Set packing
• Maximum coverage problem is to choose at most k sets to cover as many elements as possible.
• Dominating set is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown to be NP complete through a reduction from Set cover.
• Exact cover problem is to choose a set cover with no element included in more than one covering set.
• Red-blue set cover.
• Set-cover abduction.
• Monotone dualization is a computational problem equivalent to either listing all minimal hitting sets or listing all minimal set covers of a given set family.

---

Notes

• .
• .
• .
• .
• .

---

External links

• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
• A compendium of NP optimization problems - Minimum Set Cover

Post Comment